/**
 * Implements the stack data type using the array data structure.
 * 
 * @author          Maria Garcia de la Banda
 * @modified        Brendon Taylor (July 2009) - JavaDoc / Indentation / Style 
 * @modified        Brendon Taylor (Feb 2010) - JavaDoc
 * @modified        Monghong Li    (Aug 2011)
 * @since           8th March 2007
 * @invariant       (1) the top counter is never greater than theStack.length
 * @invariant       (2) all slots in positions 0 to top-1 contain stack items
 * @input           none
 * @output          only for regression testing
 * @errorHandling   none
 * @knownBugs       the toString method needs to be defined. This is something 
 *                  students need to do for the prac. Once that is done, the testing will work
 */
package prac3;
public class IntStack {   
	/** array containing the items in the stack */
	private int[] theStack;
	/**
	 * counter indicating the number of items in the stack. Since
	 * items are placed from left to right, it also indicates
	 * the first empty position in the array (if any), and top-1
	 * indicates the top of the stack.
	 */
	private int top;

	/**
	 * Creates an empty object of the class, i.e., an empty stack of integers, 
	 * Since the stack is implemented with arrays, the size is needed to 
	 * create an array of the appropriate size.
	 * 
	 * @param       size of the stack 
	 * @pre         size is positive
	 * @post        theStack is an array of the input size where each slot is 
	 *              set to 0. top is 0.
	 * @complexity  best and worst case: O(size)
	 */
	public IntStack(int size) { 
		theStack = new int[size];
		top = 0;
		for (int i = 0; i < size; i++)
			theStack[i] = 0;
	} 

	/**
	 * Used to check whether the stack is empty.
	 * 
	 * @return      isEmpty whether the stack is empty
	 * @complexity  best and worst case: O(1)
	 */
	public boolean isEmpty() {
		return (top == 0);
	}

	/**
	 * Used to check whether the stack is full.
	 * 
	 * @return      true if the stack is full, false otherwise
	 * @complexity  best and worst case: O(1)
	 */
	public boolean isFull() {
		return (top == theStack.length);
	} 

	/**
	 * Adds an element to the stack, which means it adds the input element as 
	 * the new top of the stack. If the stack is full it throws an exception.
	 * 
	 * @param       item to be pushed onto the top of the stack 
	 * @throws      Exception thrown when stack is full
	 * @post        item is added as top of the stack
	 * @complexity  best and worst case: O(1)
	 */
	public void push(int item) throws Exception {
		if (this.isFull())
			throw new Exception("Stack is full");

		theStack[top++] = item;
	}

	/**
	 * Eliminates an element from the stack, which means it removes the top 
	 * element from the stack and returns it, making the element "under it" 
	 * the new top. If the stack is empty, it throws an exception.
	 * 
	 * @return      item on top of the stack
	 * @throws      Exception thrown when stack is empty
	 * @complexity  best and worst case: O(1)
	 */
	public int pop() throws Exception {
		if (this.isEmpty())
			throw new Exception("Stack is empty");
		
		return theStack[--top];
	}

	/**
	 * Returns the element that is at the top of the stack, 
	 * if the stack is empty, it throws an exception.
	 * 
	 * @return      the top element in the stack
	 * @throws      Exception thrown when the stack is empty
	 * @complexity  best and worst case: O(1)
	 */
	public int top() throws Exception {
		if (this.isEmpty())
			throw new Exception("Stack is empty"); 
	
		return theStack[top-1];
	}

	/**
	 * Resets the stack to an empty state.
	 * 
	 * @post        the stack is empty
	 * @complexity  best and worst case: O(1)
	 */
	public void reset() {
		top = 0;
	}

	/**
	 * Prints all the elements on the stack from top to bottom.
	 * 
	 * @complexity  best and worst case: O(top). Of course, this assumes that
         *              the printing of an integer is constant.
	 */
	public void printItems() {    
		System.out.println("     The stack contains (from top to bottom):");
		System.out.print("       ");

		for (int i = top-1 ; i >= 0; i--)
			System.out.print(" "+theStack[i]);
		
		System.out.println("");
	}
	
    /**
     * Return the size of the stack
     * 
     * @pre         top exists
     * @post        the size of the stack returned
     * @complexity  best and worst case: O(1)
     */
	public int getSize(){
		return top;
	}
	
	 /**
     * Creates a string contains the numbers in the stack
     *          
     * @post        a string contains the numbers in the stack created and returned
     * @complexity  best and worst case: O(N), where N is the number of elements stored
     */
	public String toString(){
		String string = "";
    	for (int i = top-1; i >= 0; i--) {
    		string = string + theStack[i] + " ";    		
    	}
    	return string;
	}

	/*********************** REGRESSION TESTING CODE **********************/

	/**
	 * Two test cases: empty stacks and non-empty stacks 
	 * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
	 */
	private static void testIsEmpty() throws Exception {  	
		IntStack myStack = new IntStack(9);
		System.out.println("TESTING isEmpty()");
		System.out.println("Expected true, got " + myStack.isEmpty());
		myStack.push(9);
		System.out.println("Expected false, got " + myStack.isEmpty());
		myStack.push(0);
		System.out.println("Expected false, got " + myStack.isEmpty());
		myStack.push(1);
		myStack.push(2);
		myStack.push(14);
		System.out.println("Expected false, got " + myStack.isEmpty());
	}


	/**
	 * Two test cases: full stacks and non-full stacks 
	 * Boundary analysis gives five cases: 0 elements, 1, N-2, N-1, and N.
	 */
	private static void testIsFull() throws Exception {  	
		IntStack myStack = new IntStack(8);
		System.out.println("TESTING isFull()");
		System.out.println("Expected false, got " + myStack.isFull());
		myStack.push(9);
		System.out.println("Expected false, got " + myStack.isFull());
		myStack.push(0);
		myStack.push(1);
		myStack.push(2);
		myStack.push(14);
		myStack.push(20);
		System.out.println("Expected false, got " + myStack.isFull());
		myStack.push(30);
		System.out.println("Expected false, got " + myStack.isFull());
		myStack.push(40);
		System.out.println("Expected true, got " + myStack.isFull());
	}

	/**
	 * Two test cases: adding to a full stack and to non-full stacks 
	 * Boundary analysis gives five cases: 0 elements, 1, N-2, N-1, and N.
	 */
	private static void testPush() throws Exception	{  	
		IntStack myStack = new IntStack(5);
		System.out.println("TESTING push()");
		myStack.push(9);
		System.out.println("Expected 9, got " + myStack);
		myStack.push(0);
		System.out.println("Expected 0 9 , got " + myStack);
		myStack.push(1);
		myStack.push(14);
		System.out.println("Expected 14 1 0 9, got " + myStack);
		myStack.push(20);
		System.out.println("PRINTING");
		myStack.printItems();
		System.out.println("Expected 20 14 1 0 9, got " + myStack);
		System.out.print("Expected exception, ");
		
		try {
			myStack.push(30);
		}
		catch(Exception e) {
			System.out.println(e);
			return;
		}
		
		System.out.println("but none thrown");

	}

	/**
	 * Two test cases: popping from an empty stack and from a non-empty one 
	 * Boundary analysis gives five cases: 0 elements, 1, N-2, N-1, and N.
	 */
	private static void testPop() throws Exception {  	
		IntStack myStack = new IntStack(5);
		System.out.println("TESTING pop()");
		myStack.push(0);
		System.out.println("Expected 0, got " + myStack.pop());
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		System.out.println("Expected 3, got " + myStack.pop());
		myStack.push(4);
		myStack.push(5);
		System.out.println("Expected 5, got " + myStack.pop());
		myStack.push(6);
		myStack.push(7);
		System.out.println("Expected 7, got " + myStack.pop());
		myStack.pop();
		myStack.pop();
		myStack.pop();
		myStack.pop();
		System.out.print("Expected exception ");
		
		try {
			myStack.pop();
		}
		catch(Exception e) {
			System.out.println(e);
			return;
		}
		
		System.out.println("but no exception thrown");
	}

	/**
	 * Two test cases: from an empty stack and from a non-empty one 
	 * Boundary analysis gives five cases: 0 elements, 1, N-2, N-1, and N.
	 */
	private static void testTop() throws Exception {  	
		IntStack myStack = new IntStack(5);
		System.out.println("TESTING top()");
		myStack.push(0);
		System.out.println("Expected 0, got " + myStack.top());
		myStack.push(2);
		myStack.push(3);
		System.out.println("Expected 3, got " + myStack.top());
		myStack.push(5);
		System.out.println("Expected 5, got " + myStack.top());
		myStack.push(7);
		System.out.println("Expected 7, got " + myStack.top());
		myStack.pop();
		myStack.pop();
		myStack.pop();
		myStack.pop();
		myStack.pop();
		System.out.print("Expected exception ");
		
		try {
			myStack.top();
		}
		catch(Exception e) {
			System.out.println(e);
			return;
		}
		
		System.out.println("but no exception thrown");
	}

	/**
	 * Two test cases: from an empty stack and from a non-empty one 
	 * Boundary analysis gives five cases: 0 elements, 1, N-2, N-1, and N.
	 */
	private static void testReset() throws Exception {  	
		IntStack myStack = new IntStack(5);
		System.out.println("TESTING reset()");
		myStack.reset();
		System.out.println("Expected  , got "+ myStack);
		myStack.push(1);
		myStack.reset();
		System.out.println("Expected  , got "+ myStack);
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		myStack.reset();
		System.out.println("Expected  , got "+ myStack);
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		myStack.push(4);
		myStack.reset();
		System.out.println("Expected  , got "+ myStack);
		myStack.push(1);
		myStack.push(2);
		myStack.push(3);
		myStack.push(4);
		myStack.push(5);
		myStack.reset();
		System.out.println("Expected  , got "+ myStack);
	}

	/**
	 * @param       args command line arguments
	 */
	public static void main(String[] args) {
		try{
			testIsEmpty();
			testIsFull();
			testPop();
			testPush();
			testTop();
			testReset();
		}
		catch(Exception e) {
			System.out.println(e);
		}
	}
}

